package algorithm;

/**
 * @Author pc
 * @Date 2019/8/23 17:31
 * @Description kmp算法
 */
public class KMPUtil {
    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        String s = "abaabcabckfsabaabcabbabazbcabcabaabcabc";
        String p = "cabca";
        System.out.println(getIndex(s,p));
    }

    /**
     * 获取第一个匹配的下标
     * @param s
     * @param p
     * @return
     */
    public static int getIndex(String s,String p){
        char[] chars = p.toCharArray();
        int[] next = getNext(chars);
        return getIndex(s.toCharArray(),chars,next);
    }

    private static int getIndex(char[] str, char[] chars, int[] next) {
        if(chars.length==0)return 0;
        int i=0;
        int j=0;
        while(i<str.length&&j<chars.length){
            if(j==-1||str[i]==chars[j]){
                i++;
                j++;
            }else{
                j=next[j];
            }
        }
        if(j<chars.length)return -1;
        return i-j;
    }

    /**
     * 获取next数组
     */
    private static int[] getNext(char[] str){
        int[] next = new int[str.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while(j<str.length-1){
            if(k==-1||str[k]==str[j]){
                j++;
                k++;
                next[j] = k;
            }else{
                k = next[k];
            }
        }
        return next;
    }

















}